package com.zhugang.week01;

/**
 * @program algorithms
 * @description: reverseWord
 * @author: chanzhugang
 * @create: 2022/03/14 23:24
 */
public class ReverseWord {

    public static void main(String[] args) {
        ReverseWord reverseWord = new ReverseWord();
        String str = "the sky is blue";
        String reverse = reverseWord.reverseWords(str);
        System.out.println(reverse);
    }

    /**
     * 翻转单词顺序
     * "I am a student." 输出 "student. a  am I"
     * <p>
     * " hello world! "  输出 "world! hello" : 输入字符串可以在前面或者后面包含多个空格，但是翻转后不能
     * <p>
     * "a good  example" 输出 "example good a" : 如果两个单词间有多个空格，翻转后减少到只含一个
     */
    // 两次翻转：空间O(1)
    public String reverseWords(String s) {
        char[] chars = s.toCharArray();
        // 去除前置、后置、中间空格
        int n = trim(chars);
        if (n == 0) {
            return "";
        }
        // 第一次翻转
        reverse(chars, 0, n - 1);
        int p = 0;
        while (p < n) {
            int r = p;
            while (r < n && chars[r] != ' ') {
                r++;
            }
            // 第二次翻转：r-1 下标
            reverse(chars, p, r - 1);
            // 下一个单词继续
            p = r + 1;
        }
        char[] newChar = new char[n];
        for (int i = 0; i < n; i++) {
            newChar[i] = chars[i];
        }
        return new String(newChar);
    }

    /**
     * 翻转: 两种方式：1、遍历一半，交换位置； 2、双指针控制下标
     *
     * @param chars
     * @param p
     * @param r
     */
    private void reverse(char[] chars, int p, int r) {
       /* int mid = (p + r) / 2;
        for (int i = p; i <= mid; i++) {
            char temp = chars[i];
            chars[i] = chars[r - (i - p)];
            chars[r - (i - p)] = temp;
        }*/
        while (p <= r) {
            char temp = chars[p];
            chars[p] = chars[r];
            chars[r] = temp;
            p++;
            r--;
        }
    }

    /**
     * 去除前置、后置、 中间多余空格
     *
     * @param chars
     * @return
     */
    private int trim(char[] chars) {
        int n = chars.length;
        // 清除前置空格
        int i = 0;
        while (i < n && chars[i] == ' ') {
            i++;
        }
        // 清除后置空格
        int j = n - 1;
        while (j >= 0 && chars[j] == ' ') {
            j--;
        }
        // 清除内部多余空格，并且把i-j之间的字符搬移到数组最前面 ： // a good   example  :
        int k = 0;
        while (i <= j) {
            if (chars[i] == ' ') {
                if (i + 1 <= j && chars[i + 1] != ' ') {
                    chars[k++] = ' ';
                }
            } else {
                chars[k++] = chars[i];
            }
            i++;
        }
        return k;
    }
}